package Tree;

public class HeroTree {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Hero hero1 = new Hero(1, "Song");
        Hero hero2 = new Hero(2, "WU");
        Hero hero3 = new Hero(3, "Lu");
        Hero hero4 = new Hero(4, "Lin");
        Hero hero5 = new Hero(5, "Guan");
        Hero hero6 = new Hero(6, "Lu");
        Hero hero7 = new Hero(7, "Chenyigou");
        hero1.setLeft(hero2);
        hero1.setRight(hero3);
        hero2.setLeft(hero6);
        hero2.setRight(hero7);
        hero3.setLeft(hero5);
        hero3.setRight(hero4);
        binaryTree.setRoot(hero1);
        System.out.println("前序遍历");
        binaryTree.preOrder();
//        System.out.println("中序遍历");
//        binaryTree.minOrder();
//        System.out.println("后序遍历");
//        binaryTree.latterOrder();
//        System.out.println("查找");
//        Hero hero = binaryTree.preSeach(5);
//        System.out.println("查找的为："+hero);
//        Hero hero6 = binaryTree.minSeach(5);
//        System.out.println("中："+hero6);
//        Hero hero7 = binaryTree.latterSeach(5);
//        System.out.println("后："+hero7);
//        binaryTree.setRoot(hero1);
//        int i = binaryTree.calculateHigh();
//        System.out.println(i);
//        System.out.println("删除前：");
//        binaryTree.preOrder();
//        binaryTree.deleteByno(5);
//        System.out.println("删除后:");
//        binaryTree.preOrder();
//        binaryTree.setRoot(hero1);
//        binaryTree.preOrder();
//        int i = binaryTree.calculateJieDian();
//        int i = binaryTree.calculateYeZiJieDian();
//        int i = binaryTree.calculateHigh();
//        System.out.println("高度："+i);
//        binaryTree.levelorder();
    }
}
//创建树
class BinaryTree{
    private Hero root;
    //根节点
    public void setRoot(Hero root) {
        this.root = root;
    }


    //前序遍历：
    public void preOrder(){
        if(root!=null){
            root.preOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //中序遍历：
    public void minOrder(){
        if(root!=null){
            root.minOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //后序遍历：
    public void latterOrder(){
        if(root!=null){
            root.latterOrder();
        }else {
            System.out.println("当前二叉树为空~~~~");
        }
    }
    //前查找：
    public Hero preSeach(int no){
        if(root!=null){
            return root.preReseachNo(no);
        }else {
            return null;
        }
    }
    //中查找：
    public Hero minSeach(int no){
        if(root!=null){
            return root.minReseachNo(no);
        }else {
            return null;
        }
    }
    //后查找
    public Hero latterSeach(int no){
        if(root!=null){
            return root.latterReseachNo(no);
        }else {
            return null;
        }
    }
    //根据编号删除
    public void deleteByno(int no) {
        if (root == null) {
            System.out.println("这是空树，无法删除");
        } else {
            if (root.getHeroNo() == no) {
                root = null;
                return;
            } else {
                root.deleteTreeByNo(no);
            }
        }
    }
    //计算高度
    public int calculateHigh(){
        if (root==null){
            return 0;
        }else {
            return root.calculateHigh(root);
        }
    }
    //计算结点
    public int calculateJieDian(){
        if(root==null){
            return 0;
        }else {
            return root.calculateJieDian(root);
        }
    }
    //计算叶子节点
    public int calculateYeZiJieDian(){
        if (root==null){
            return 0;
        }else {
            return root.calculateYeZiJieDian(root);
        }
    }
    //层次遍历
    public void levelorder()
    {
        System.out.println("This binaryTree is:");
        SeqQueue que=new SeqQueue();
        Hero p = root;
        while (p!=null)
        {
            System.out.println(p);
            if (p.getLeft()!=null)
                que.add(p.getLeft());
            if (p.getRight()!=null)
                que.add(p.getRight());
            p= (Hero) que.poll();
        }
        System.out.println();
    }
}
//树的结点元素
class Hero {
    private int heroNo;
    private String eroName;
    private Hero Left;
    private Hero Right;

    public Hero(int heroNo, String eroName) {
        this.heroNo = heroNo;
        this.eroName = eroName;
    }

    public int getHeroNo() {
        return heroNo;
    }

    public void setHeroNo(int heroNo) {
        this.heroNo = heroNo;
    }

    public String getEroName() {
        return eroName;
    }

    public void setEroName(String eroName) {
        this.eroName = eroName;
    }

    public Hero getLeft() {
        return Left;
    }

    public void setLeft(Hero left) {
        Left = left;
    }

    public Hero getRight() {
        return Right;
    }

    public void setRight(Hero right) {
        Right = right;
    }

    @Override
    public String toString() {
        return "Hero{" +
                "heroNo=" + heroNo +
                ", eroName='" + eroName + '\'' +
                '}';
    }

    //前序输出
    public void preOrder() {
        System.out.println(this);
        if (this.getLeft() != null) {
            this.getLeft().preOrder();
        }
        if (this.getRight() != null) {
            this.getRight().preOrder();
        }
    }

    //中序输出
    public void minOrder() {
        if (this.getLeft() != null) {
            this.getLeft().minOrder();
        }
        System.out.println(this);
        if (this.getRight() != null) {
            this.getRight().minOrder();
        }
    }

    //后序输出
    public void latterOrder() {
        if (this.getLeft() != null) {
            this.getLeft().minOrder();
        }
        if (this.getRight() != null) {
            this.getRight().minOrder();
        }
        System.out.println(this);
    }

    //前查找
    public Hero preReseachNo(int no) {
        System.out.println("进入了前序遍历~~");
        if (this.getHeroNo() == no) {
            return this;
        }
        Hero hero = null;
        if (this.getLeft() != null) {
            hero = this.getLeft().preReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        if (this.getRight() != null) {
            hero = this.getRight().preReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        return hero;
    }

    //中查找
    public Hero minReseachNo(int no) {
        Hero hero = null;
        if (this.getLeft() != null) {
            hero = this.getLeft().minReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        System.out.println("进入了中序遍历~~");
        if (this.getHeroNo() == no) {
            return this;
        }
        if (this.getRight() != null) {
            hero = this.getRight().minReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        return hero;
    }
    //后序查找
    public Hero latterReseachNo(int no) {
        Hero hero = null;
        if (this.getLeft() != null) {
            hero = this.getLeft().latterReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        if (this.getRight() != null) {
            hero = this.getRight().latterReseachNo(no);
        }
        if (hero != null) {
            return hero;
        }
        System.out.println("进入了后序遍历");
        if (this.getHeroNo() == no) {
            return this;
        }
        return hero;
    }

    //删除节点:
    public void deleteTreeByNo(int no) {
        if (this.getLeft() != null) {
            if (this.getLeft().getHeroNo() == no) {
                this.setLeft(null);
                return;
            }
        }
        if (this.getRight() != null) {
            if (this.getRight().getHeroNo() == no) {
                this.setRight(null);
                return;
            }
        }
        if (this.getLeft() != null) {
            this.getLeft().deleteTreeByNo(no);
        }
        if (this.getRight() != null) {
            this.getRight().deleteTreeByNo(no);
        }
    }
    //计算高度
    public int calculateHigh(Hero hero) {
        int left = 0;
        int right = 0;
        if (hero.getLeft() != null) {
            left = calculateHigh(hero.getLeft());
        }
        if (hero.getRight() != null) {
            right = calculateHigh(hero.getRight());
        }
        return left > right ? ++left : ++right;
    }
    //计算结点
    public int calculateJieDian(Hero hero) {
        int lSize = 0;
        int rSize = 0;
        if (hero.getLeft() != null) {
            lSize = calculateJieDian(hero.getLeft());
        }
        if (hero.getRight() != null) {
            rSize = calculateJieDian(hero.getRight());
        }
        return lSize + rSize + 1;
    }
    //计算子节点
    public int calculateYeZiJieDian(Hero hero) {

        if(hero.getLeft()==null||hero.getRight()==null){
            return 1;
        }
        return calculateYeZiJieDian(hero.getLeft())+calculateYeZiJieDian(hero.getRight());
    }

}

